<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var nums = [1, 2, 3, 3, 3, 5];
      // 二分搜索
      function binary_search(nums, target) {
        // 闭区间方式
        var left = 0;
        var right = nums.length - 1;

        while (left <= right) {
          var mid = Math.floor((left + right) / 2);
          if (nums[mid] == target) {
            return mid;
            // 找到目标
          } else if (nums[mid] < target) {
            // 说明目标在 mid---right 之间
            left = mid + 1;
          } else if (nums[mid] > target) {
            // 说明目标 在 left----mid之间
            right = mid - 1;
          }
        }
        // 没找到返回 -1
        return -1;
      }
      console.log(binary_search(nums, 0));

      // 二分搜索 左侧边界
      function left_bound(nums, target) {
        // 闭区间
        var left = 0;
        var right = nums.length - 1;
        while (left <= right) {
          var mid = Math.floor((left + right) / 2);
          if (nums[mid] < target) {
            left = mid + 1;
          } else if (nums[mid] > target) {
            right = mid - 1;
          } else if (nums[mid] == target) {
            // 要找左侧边界
            right = mid - 1;
          }
        }
        // 如果 目标 小于 所有值,right 会一直减小,直到循环停止 此时 right会是-1 left 是0 ,,此时若nums[0]不是目标,就应返回-1
        // 如果目标 大于所有值 , left 会一直增长 ,增长到 length 大于right的length-1(停止),length已经越界,所以此时返回-1
        if (nums[left] != target || left == nums.length) {
          return -1;
        } else {
          return left;
        }
      }
      console.log(left_bound(nums, 3));

      // 二分搜索右边界

      function right_bound(nums, target) {
        var left = 0;
        var right = nums.length - 1;
        while (left <= right) {
          var mid = Math.floor((left + right) / 2);
          if (nums[mid] < target) {
            left = mid + 1;
          } else if (nums[mid] > target) {
            right = mid - 1;
          } else if (target == nums[mid]) {
            // 找右边界
            left = mid + 1;
          }
        }
        // 特殊情况

        // 如果 目标小于所有值 ,right一直减小,最终减小到-1 停止,下标越界  返回-1
        // 如果 目标大于所有值,left 会一直增长,增长到 比 right(length-1) 多1 结束,,,如果nums[right]==target 返回right即可,否则 此时 返回-1
        if (right < 0 || nums[right] != target) {
          return -1;
        } else {
          return right;
        }
      }
    </script>
  </body>
</html>
